package com.wuxuan.algorithm_homework.treeNode;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 二叉树II
 *
 * 二叉树的路径
 * 二叉树的构建
 * 二叉树的最近公共祖先
 *
 * 总结树的解题步骤：
 * 1.当前节点从左子树拿些信息，也从右子树拿些信息
 * 2.当前节点对拿到的信息做整合
 * 3.返回什么信息给父节点
 *
 */
public class TreeNode2 {

    /**
     * 二叉树的路径
     * 给定一个二叉树，返回从一个叶子节点到另一个叶子节点的最大路径的和
     * @param root
     * @return
     */
    public int maxSum1(TreeNode root) {
        //思：我不理解，为什么一定要放到数组里面？int是基本类型然后传递的不是内存地址而是只是复制了一份值，我可以理解。但是Integer不是引用类型吗？传递的不是指针吗也就是内存地址，为什么不行？
        //答：Integer是引用类型，但它的行为类似于不可变对象
        //在Java中，Integer是一个包装类，它封装了一个基本数据类型int的值。虽然Integer是引用类型，但它是一个不可变对象。这意味着一旦一个Integer对象被创建，它的值就不能被改变。
        //不可变对象的一个重要特性是，每次对它的修改都会创建一个新的对象。这意味着你在递归调用中对Integer的修改不会影响到上层调用中的变量。
        //数组和自定义类是可变对象，它们的引用在递归调用中保持不变。这意味着你可以通过修改数组或自定义类中的值来更新全局状态。
        //综上，这里使用了数组来存储result！！！
        int[] result = {Integer.MIN_VALUE};
        findMaxSum1(root, result);
        return result[0];
    }

    private int findMaxSum1(TreeNode root, int[] result) {
        if (root == null) {
            return 0;
        }

        //当前节点从左子树拿些信息，也从右子树拿些信息
        int left = findMaxSum1(root.left, result);
        int right = findMaxSum1(root.right, result);

        //当前节点对拿到的信息做整合
        //如果当前节点左子树和右子树都不为空
        if (root.left != null && root.right != null) {
            //更新全局最大路径和
            result[0] = Math.max(result[0], left + right + root.val);
            //返回当前节点的最大贡献值给父节点
            return root.val + Math.max(left, right);
        }

        //如果当前节点只有一个子树，返回当前节点+那个子树的最大贡献值
        //如果没有子树，返回当前节点的值
        return root.left == null ? root.val + right : root.val + left;
    }

    @Test
    public void testMaxSum1() {
        //自创一个二叉树
        TreeNode root = new TreeNode(12);
        root.left = new TreeNode(-5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(10);
        root.left.left.left = new TreeNode(0);
        root.left.right.right = new TreeNode(-2);
        root.right.right.left = new TreeNode(1);

        System.out.println(maxSum1(root));
    }

    /**
     * 二叉树的路径
     * 给定一个二叉树，返回从任意一个节点到另一个节点的最大路径的和
     * 注：单个节点也满足条件
     * @param root
     * @return
     */
    public int maxSum2(TreeNode root) {
        int[] result = {Integer.MIN_VALUE};
        findMaxSum2(root, result);
        return result[0];
    }

    private int findMaxSum2(TreeNode root, int[] result) {
        if (root == null) {
            return 0;
        }
        //拿到左子树的Max
        int left = Math.max(findMaxSum2(root.left, result), 0);
        //拿到右子树的Max
        int right = Math.max(findMaxSum2(root.right, result), 0);

        //更新全局最大路径和
        result[0] = Math.max(result[0], left + right + root.val);

        //整合当前节点的Max传给父节点
        int currentMax = Math.max(0, left) + Math.max(0, right) + root.val;

        return Math.max(0, currentMax);
    }

    @Test
    public void testMaxSum2() {
        //自创一个二叉树
        TreeNode root = new TreeNode(12);
        root.left = new TreeNode(-5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(10);
        root.left.left.left = new TreeNode(0);
        root.left.right.right = new TreeNode(-2);
        root.right.right.left = new TreeNode(1);

        System.out.println(maxSum2(root));
    }

    /**
     * 二叉树的构建
     *
     * 给定两个整数数组 preorder和inorder，其中 preorder是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * preorder 和 inorder 均无重复元素。
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return buildTreeHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, map);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder,int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> map) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        int i = map.get(preorder[preStart]);

        //新的左子树中:
        //分析其在preorder和inorder中的左右边界！！！
        //preorder:
        //左边界 = preSrart + 1
        //右边界 = preorder左边界 + 左子树的长度(inorder中 根节点（即i）左边的长度 : i - 1 - inStart) = preStart + 1 + i - 1 - inStart = preStart - inStart + i
        //inorder:
        //左边界 = inStart
        //右边界 = i - 1

        //新的右子树中:
        //preorder:
        //左边界 = 左子树的右边界 + 1 = preStart - inStart + i + 1
        //右边界 = preEnd
        //inorder:
        //左边界 = i + 1
        //右边界 = inEnd

        root.left = buildTreeHelper(preorder, inorder, preStart + 1, preStart - inStart + i, inStart, i - 1, map);
        root.right = buildTreeHelper(preorder, inorder, preStart - inStart + i + 1, preEnd, i + 1, inEnd, map);

        return root;
    }


    @Test
    public void testBuildTree() {
//        //自创一个二叉树
//        TreeNode root = new TreeNode(12);
//        root.left = new TreeNode(5);
//        root.right = new TreeNode(15);
//        root.left.left = new TreeNode(3);
//        root.left.right = new TreeNode(7);
//        root.right.left = new TreeNode(13);
//        root.right.right = new TreeNode(20);
        int[] preorder = {12, 5, 3, 7, 15, 13, 20};
        int[] inorder = {3, 5, 7, 12, 13, 15, 20};

        TreeNode root = buildTree(preorder, inorder);

        //层次遍历一下粗略看看结果对不对
        TreeNodeDemo treeNodeDemo = new TreeNodeDemo();
        List<List<Integer>> result = treeNodeDemo.levelOrder(root);

        System.out.println(result);
    }


    /**
     * 二叉树的最近公共祖先
     *
     * 给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
     * 最近公共祖先的定义为:“对于有根树T的两个节点 p、q，最近公共祖先表示为一个节点x，满足x是 p、q 的祖
     * 先且x的深度尽可能大(一个节点也可以是它自己的祖先)”,p,q 都在二叉树中
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return findLowestCommonAncestor(root, p, q);

    }

    private TreeNode findLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //基本情况：
        //如果当前节点为空（root == null），返回null。
        //如果当前节点是p或q中的一个（root == p或root == q），返回当前节点。

        if (root == null || root == p || root == q) {
            return root;
        }

        //从左右节点获取一些信息，看左边子树和右边子树是否为空
        //递归计算左右子树：
        //从当前节点的左子树中找p和q的最近公共祖先。
        TreeNode left = findLowestCommonAncestor(root.left, p, q);
        //从当前节点的右子树中找p和q的最近公共祖先。
        TreeNode right = findLowestCommonAncestor(root.right, p, q);

        //整合信息：
        if (left != null && right != null) {
            //如果左子树和右子树都找到了p或q，那么当前节点就是最近公共祖先。
            return root;
        } else if (left != null) {
            //如果只在左子树中找到了p或q，那么左子树的结果就是最近公共祖先。
            return left;
        } else {
            //如果只在右子树中找到了p或q，那么右子树的结果就是最近公共祖先。
            return right;
        }
    }

    @Test
    public void testLowestCommonAncestor() {
//        自创一个二叉树
        TreeNode root = new TreeNode(12);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(20);

        //5和15的最近公共祖先？
        TreeNode result1 = lowestCommonAncestor(root, root.left, root.right);
        System.out.println(result1.val);

        //5和7的最近公共祖先？
        TreeNode result2 = lowestCommonAncestor(root, root.left, root.left.right);
        System.out.println(result2.val);

    }

}
